#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<string>
using namespace std;
template <class T>
class list {
private:
	T data;
	list* next;
	list* last;
public:
	list(T _data = 0) {
		data = _data;
		next = nullptr;
		last = nullptr;
	}
	~list() {}
	void push_back(T _data = 0) {
		list* tmp = this;
		while (tmp->next)tmp = tmp->next;
		tmp->next = new list(_data);
		tmp->next->last = tmp;
	}
	list* push_head(T _data = 0) {
		list* tmp = new list(_data);
		tmp->next = this;
		this->last = tmp;
		return tmp;
	}
	void print() {
		list* tmp = this;
		while (tmp) {
			cout << tmp->data << " ";
			tmp = tmp->next;
		}
		cout << endl;
	}
	void append(list<T>& l) {
		list* tmp1 = this;
		list* tmp2 = &l;
		while (tmp1 && tmp2) {
			if (tmp1->data < tmp2->data) {
				tmp1 = tmp1->next;
			}
			else {
				list* tmp = tmp1->last;
				tmp->next = tmp2;
				tmp2->last = tmp;
				tmp1->last = tmp2;
				tmp2 = tmp2->next;
				tmp->next->next = tmp1;
			}
		}
		if (tmp2) {
			tmp1 = this;
			while (tmp1->next) {
				tmp1 = tmp1->next;
			}
			tmp1->next = tmp2;
		}
	}
};
int main() {
	list<int> l1(1);
	list<int> l2(2);
	l1.push_back(3);
	l1.push_back(5);
	l1.push_back(7);
	l1.push_back(9);
	l2.push_back(4);
	l2.push_back(5);
	l2.push_back(8);
	l2.push_back(10);
	l1.print();
	l2.print();

	l1.append(l2);
	l1.print();

	return 0;
}